package tplenguajes.grafo;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class AFD<T> extends FiniteAutomata<T>
{
	public AFD(AFND<T> afnd)
	{
		super(afnd.getAlphabet());
		
		conversionIterativa(afnd);
	}
	
	public boolean acceptsString(Iterable<T> string)
	{
		AutomataState currentState = this.getRoot();
		
		for ( T transition : string )
		{
			currentState = getEdges(currentState).getTarget(transition);
			if ( currentState == null ) return false;
		}
		
		if ( !currentState.isFinal() )
			return false;
		
		return true;
	}
	
	private void conversionIterativa(AFND<T> afnd)
	{
		Map<AutomataState,Set<AutomataState>> stateMap = new HashMap<AutomataState, Set<AutomataState>>();
		
		Stack<AutomataState> stack = new Stack<AutomataState>();
		
		Set<AutomataState> rootSet = new HashSet<AutomataState>(); rootSet.add(afnd.getRoot());
		Set<AutomataState> initialClosure = afnd.getEpsilonClosure(rootSet);
		
		stateMap.put(this.getRoot(), initialClosure);
		stack.push(this.getRoot());
		if( afnd.isFinalClosure(initialClosure) )
			this.getRoot().setAsFinal();
		
		while (!stack.isEmpty())
		{
			AutomataState state = stack.pop();
			
			// TODO Me parece bastante poco performante iterar sobre todo el alfabeto
			// sera mejor armar el conjunto de posibles transiciones del conjunto de estados?
			for ( T transition : getAlphabet() )
			{
				Set<AutomataState> sources = stateMap.get(state);
				Set<AutomataState> targets = afnd.getTargets(sources, transition);
				
				if (!targets.isEmpty())
				{
					Set<AutomataState> potentialNewClosure = afnd.getEpsilonClosure(targets);
					
					AutomataState potentialNewState = stateThatContains(potentialNewClosure, stateMap);
					
					if ( potentialNewState == null )
					{
						potentialNewState = new AutomataState();
						this.addVertex(potentialNewState);
						
						stateMap.put(potentialNewState, potentialNewClosure);
						stack.push(potentialNewState);
						
						if( afnd.isFinalClosure(potentialNewClosure) )
							potentialNewState.setAsFinal();
					}
					
					addStateTransition(state, potentialNewState, transition);
				}
			}
		}
	}
	
	private AutomataState stateThatContains(Set<AutomataState> closure, Map<AutomataState,Set<AutomataState>> states)
	{
		for ( AutomataState key : states.keySet() )
			if (closure.equals(states.get(key)))
				return key;
		
		return null;
	}
	
	private boolean addStateTransition(AutomataState src, AutomataState dst, T transition)
	{
		return this.addEdge(src, dst, new StateTransition<T>(src, dst, transition));
	}
	
	@Override protected Edges getNewEdges() { return new AFDEdges(); }
	@Override protected AFDEdges getEdges(AutomataState v) { return (AFDEdges)super.getEdges(v); }
	
	protected class AFDEdges extends Edges
	{
		private Map<T,Edge<AutomataState>> incoming = new HashMap<T, Edge<AutomataState>>();
		private Map<T,Edge<AutomataState>> outgoing = new HashMap<T, Edge<AutomataState>>();
        
		@Override public void addIncomingEdge(Edge<AutomataState> e) { incoming.put(getLabel(e),e); }
		@Override public void addOutgoingEdge(Edge<AutomataState> e) { outgoing.put(getLabel(e),e); }
		
		@Override public void removeIncomingEdge(Edge<AutomataState> e) { incoming.remove(getLabel(e)); }
		@Override public void removeOutgoingEdge(Edge<AutomataState> e) { outgoing.remove(getLabel(e)); }
        
        @Override public Set<Edge<AutomataState>> getIncoming() { return getValueSet(incoming); }
        @Override public Set<Edge<AutomataState>> getOutgoing() { return getValueSet(outgoing); }
		
        public AutomataState getTarget(T transition)
        {
        	Edge<AutomataState> edge = outgoing.get(transition);
        	return (edge==null) ? null : edge.getTarget();
        }
        
		private Set<Edge<AutomataState>> getValueSet(Map<T, Edge<AutomataState>> map)
		{
			Set<Edge<AutomataState>> result = new HashSet<Edge<AutomataState>>();
			
			for ( T t : map.keySet() )
				result.add(map.get(t));
			
			return result;
		}
		
		private T getLabel(Edge<AutomataState> e) { return ((StateTransition<T>)e).getLabel(); }
	}
}
